import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution1096 {

    int pre=1;

    public List<String> braceExpansionII(String expression) {
        expression="{".concat(expression).concat("}");
        List<String> list=new ArrayList<>(dfs(expression));
        list.sort(String::compareTo);
        return list;
    }

    private Set<String> dfs(String expression) {
        Set<String> set=new HashSet<>();
        Set<String> now=new HashSet<>();
        String t="";
        while (expression.charAt(pre)!='}'){
            if (expression.charAt(pre)=='{'){
                pre++;
                Set<String> m=dfs(expression);
                if (t.equals("") && now.isEmpty()){
                    now=m;
                }else if (!t.equals("")){
                    for (String s : m) {
                        now.add(t.concat(s));
                    }
                    t="";
                }else{
                    Set<String> n=new HashSet<>();
                    for (String s : now) {
                        for (String s1 : m) {
                            n.add(s.concat(s1));
                        }
                    }
                    now=n;
                }
            }else if (expression.charAt(pre)==','){
                if (!t.equals("")){
                    set.add(t);
                    t="";
                }else{
                    set.addAll(now);
                    now.clear();
                }
                pre++;
            }else{
                if (now.isEmpty()){
                    t=t.concat(String.valueOf(expression.charAt(pre)));
                }else {
                    Set<String> n=new HashSet<>();
                    for (String s : now) {
                        n.add(s.concat(String.valueOf(expression.charAt(pre))));
                    }
                    now=n;
                }
                pre++;
            }
        }
        pre++;
        if (!t.equals("")){
            set.add(t);
        }else if (!now.isEmpty()){
            set.addAll(now);
        }
        return set;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1096().braceExpansionII("{{a,z},a{b,c},{ab,z}}"));
    }
}
